class Solution
{
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        int m = text1.size();
        int n = text2.size();
        // dp[i][j]
        // text1中【0到i结尾的最长公共子序列（注意，最长公共子序列不一定是i结尾，可能是前面）】
        // text2中【0到j结尾的最长公共子序列（注意，最长公共子序列不一定是j结尾，可能是前面）】
        // 我们多开一行加上一列的虚拟空间，加上引入空串的概念，最长公共子序列是空串，长度为0
        // 所以结合以上种种 加上我们的二维dp表后续填表分析，初始化为0就行
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        text1 = " " + text1; // 前面加上一个辅助字符，那么字符串的下标就与二维dp的正文下标对应上了，屏蔽虚拟空间位置了
        text2 = " " + text2;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                // if(text1[i-1] == text2[j-1])
                // 将两个字符串前面加了一个空格，那么这里的下标就和虚拟空间对应上了
                if (text1[i] == text2[j])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    // dp[i][j] = max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));
                    // 因为dp[i-1][j]和dp[i][j-1]都包含了dp[i-1][j-1]这个范围，所以不需要进行处理了
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // 返回t1表0到m结尾，t2表0到n结尾的最长公共子序列
        return dp[m][n];
    }
};
class Solution
{
public:
    int maxUncrossedLines(vector<int> &nums1, vector<int> &nums2)
    {
        // 这一题我们看题目给的实例会发现，n1和n2最终连线的值就是n1和n2的最长公共子序列！ P1143题
        // 只不过这题是数组，那一题是字符串！
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (nums1[i - 1] == nums2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
};
class Solution
{
public:
    int numDistinct(string s, string t)
    {
        // dp[i][j]表示 ： 在s[0到j]区间中的【子序列中】，有多少个t[0到i]区间的【子串】
        int m = t.size();
        int n = s.size();
        s = " " + s;
        t = " " + t;
        // 下面+=可能超过int大小了，所以这里用一个double
        vector<vector<double>> dp(m + 1, vector<double>(n + 1));
        // t如果是空串，那么s的子序列里面一定有一个t【dp[0][j]全是1】
        for (int j = 0; j <= n; ++j)
            dp[0][j] = 1;
        // s如果是空串，那么t如果为空串结果为0【初始化全为0】，否则就继续计算【下面代码进行计算】
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                // 包含s[j],且t[i] == s[j]
                // 加的t中的i位置和s中的j位置是【加在前面情况的后面的，所以不能加1】
                // dp[i-1][j-1]
                if (t[i] == s[j])
                    dp[i][j] += dp[i - 1][j - 1]; // 求最多个数，要加起来
                // 不包含s[j]
                // dp[i][j-1]
                dp[i][j] += dp[i][j - 1];
            }
        }
        // return dp[m][n] %= (int)(pow(10,9) + 7); 需要取模，pow是浮点数要转换类型
        return dp[m][n];
    }
};